home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programmierung
/
Power-Programmierung (Tewi)(1994).iso
/
magazine
/
c_news
/
15
/
cnews015.doc
next >
Wrap
Text File
|
1989-07-05
|
39KB
|
1,224 lines
Issue 15 C News 1
*-------------------------------------------------------------*
| C NEWS - International C Electronic Newsletter/Journal |
| "Dedicated to the Art of C Programming" |
| |
| Founded 12/27/87 |
*-------------------------------------------------------------*
Table of Contents
Heap: A Message from the Editor ............................. 2
Linked Lists: An Introduction by A. Lander .................. 4
Beginners Corner: By W.Dernoncourt ..........................12
Beginners Corner Pt II: By W.Dernoncourt ....................15
Attachments .................................................20
"C News" is an Electronic Journal published by the C BBS in
Burke, VA on a monthly basis. The subject for C News is the C
programming language, as well as any derivatives like C++.
All readers are encouraged to submit articles, reviews, or
comments for submission. C News is freely distributed, but can
not be sold for a profit, or cannot have a charge assessed to
cover distribution costs. All articles, and reviews become the
property of C News and cannot be included in other
publications without written permission from the C News
Editorial Staff. To do so is in direct violation of the C News
License agreement. Copies of which are available from the C
BBS. This publication is Copyrighted under U.S Copyright
Law.
Issue 15 C News 2
================================================================
THE HEAP: MESSAGES FROM THE EDITOR
================================================================
HELLO AGAIN!!!
After quite a few months, "C News" finally hits the digital
data streams again. Here at the C BBS we have suffered through
hardrive crashes, turmoil, and general burnout. But I am happy
to report that we are back, and ready to continue publishing C
News.
Over the last couple of weeks, numerous letters, postcards, and
electronic mail messages have been received asking the status
of C News. I thank all of you for your support, and it is
because of this I plan to continue with C News.
[ Changes with C News ]
There have been two changes that I would like to discuss with
you at this time. One, C News will no longer attempt to adhere
to a strict publication schedule. Due to severe time
constraints I will be unable to support C News (and the C BBS)
as much as I have in the past. However, in an attempt to help
out with the creation and publication of C News each month or
so. Two long time C News Readers and C BBS Users have joined
the editorial staff: Dan Kozak and Jim Singleton. Both Dan and
Jim have been readers of C News and users of the C BBS since
the beginning, and have volunteered to help with the monthly
publication of the newsletter. I welcome both Dan and Jim to
the group and hope that you will as well.
[ What's in this issue...]
This issue of C News features an article by Anthony Lander on
Linked Lists, continuation of Wayne Dernoncourts Beginner's
column, and a product review by Jim Singleton. I will refrain
from mentioning what will be in the next issue as the contents
have not been firmed up at this time.
[ Help!! ]
The editorial staff of C News needs some assistance. Wanted
are articles on C or C++ programmimng under MS-DOS, UNIX,
MINIX, Amiga-DOS, or your homebrew op system. See the
attachment on "How to Contact C News" for more information on
how to contact us here at the C BBS.
Issue 15 C News 3
[ Postcards!!! ]
Still looking for postcards from readers of C News. Since the
last issue of C News, numerous postcards have been received
from around the globe. Still looking for some from the United
States, as the Rest of the Globe is currently in the lead.
Well, until next month, C ya
Barry
Issue 15 C News 4
===============================================================
LINKED LISTS: AN INTRODUCTION BY ANTHONY LANDER
===============================================================
1 What is a Linked List?
A linked list is a structure, which looks like a iron link
chain, inside your computer memory, or on a disk. Linked lists
are good ways to store data when the data has to remain in a
certain order, but has be changed frequently. You can insert,
delete, and move your data around very quickly without having
to shuffle and resort your entire data set.
Let's look at the chain analogy a little closer. Imagine that
each link in the chain represents one element of data. The
data is stored this way, linked together, so that you can
follow along the chain very quickly and easily. With a
computer it's very easy to cut links out of the chain, add new
links in, wherever we feel like it, or move links to differnt
places in the chain.
There are two varieties of linked lists, singly linked and
doubly linked. A singly linked list consists of structures
which contain elements of data, and a pointer to the next
element in the list. A doubly linked list consists of a
pointer to the next element and the previous element in the
list.
Our library deals with doubly linked lists because you can move
both ways along the chain, forward and backward. Doulby
linked lists are more suited to most applications, and,
besides, a singly linked list is really just a subset of a
doubly linked one.
Graphically, a doubly linked list looks something like this:
-------------- -------------- --------------
--> | |-------> | |-------> | |
| Data 1 | | Data 2 | | Data 3 |
| | | | | |
----| | <-------| | <-------| |
-------------- -------------- --------------
Though I didn't illustrate it, a very important aspect of
linked lists is that 'Data 1' doesn't necessarily have to
physically precede 'Data 2', it just has to point to it!
The practical upshot of this is this: if, for example, you
Issue 15 C News 5
wanted to delete 'data 2', all you'd have to do is point 'Data
1's ---> forward arrow to 'Data 3', and 'Data 3's <--- backward
arrow to 'Data 1'. By doing this, 'Data 2' is never accessed,
because the pointers skip right over it. You never have to
resort your list because nothing ever moves, physically.
Graphically, removing 'Data 2' would look like this:
-------------- . . . . . . . . --------------
--> | |------------------------------> | |
| Data 1 | . D a t a 2 . | Data 3 |
| | . . | |
----| | <------------------------------| |
-------------- . . . . . . . . --------------
Similarly, you can insert data elements. Let's say we wanted
to put 'Data 2' between 'Data 6' and 'Data 7'. This is what it
would look like when you put 'Data 2' back in place:
--------------
,----> | |-----,
| | Data 2 | |
| | | |
| ,--| | <-, |
| | -------------- | |
-------------- | | | | --------------
--> | |--' | | '--> | |
| Data 6 | | | | Data 7 |
| | | | | |
----| | <----' '------| |
-------------- --------------
2 When would you use a linked list?
Linked lists are a good choice whenever you have to insert,
delete, move move elements around frequently, but always keep
Issue 15 C News 6
them in a particular order.
Examples of linked lists are:
- The malloc() and free() functions that allocate and
deallocate blocks of contiguous memory in 'C.
- Database applications (the pointers can point to file
records just as easily as locations in computer memory).
- Text editors which have to insert, delete, and move lines
of text, but keep the file in order.
Issue 15 C News 7
3 The Library
The file LINE.ZOO contains the following files:
example.c A small 'c program to demonstrate the use of the
library.
example.exe An executable example file.
line.c The actual functions that compose the library.
line.h An #include file, with the structure for our
linked list, and some #defines as well.
fprot.h Function prototypes for all the functions in the
library.
line.obj line.c compiled with Microsoft C 5.1.
Though the library is written in Microsoft 'C 5.1, it should
port to other compilers, and operating systems easily. It only
calls functions the standard library functions malloc() and
free(), everything else is done through the manipulation of
pointers.
The functions are written around a text processing application,
though it would be easy to change that to suit whatever data
you're working with. The elements stored in our structure are
a line of text, and it's length.
3.1 The Structure
Let's start off by examining the structure that holds each
element in the linked list.
struct line {
char *string; /* Text of the line */
int length; /* Length of the line */
struct line *prevline; /* PTR to struct of prev line */
struct line *nextline; /* PTR to struct of next line */
};
Issue 15 C News 8
string is a pointer to a line of text, and length is the length
of the text line. These are both data elements, and are not
really related to the mechanics of the linked list.
It may look weird, at first glance, to see a structure of type
line defined inside a structure of type line. Remember,
though, prevline and nextline are only pointers, not structures
themselves.
--------------
. . .----> | |-----> nextline
| Data X |
| |
prevline <----| | <----. . .
--------------
Examining the X'th data element, we find that prevline points
to previous data element, which would be the X-1'th. nextline
points to the next data element, in this case that's the
X+1'th.
If X were the FIRST element in the list, prevline would point
to NULL, or the -1th file record to indicate that we're at one
end of the list. Likewise if X were the LAST element, nextline
would point to NULL or the -1th file element to show that we're
at the other end of the list.
3.2 The Functions
The functions in the library can be broken down into 4
categories. Let's take a look at them one by one.
This first group of functions do not manipulate the position of
the lines in any way.
getnewline
Call this function whenever you want to put data into a new
structure. This function returns a pointer to a struct line,
which has been given space through malloc(). If there wasn't
enough space to create a line, then the function returns NULL.
This doesn't actually insert the line into the linked list, it
Issue 15 C News 9
just gets some space for it, and makes sure that the prevline
and nextline pointers are set to NULL. Inserting lines into
the text comes later.
[getfirstline, and getlastline]
getfirstline() returns the first link in the chain, and
getlastline() returns the last link in the chain. If there are
no elements in the chain, both of these functions will return
NULL.
This next group of functions are used to insert elements into
the list. It's easier to think of it as adding links into the
middle of a chain.
[insertafterline]
This function will take a struct line, returned by
getnewline(), and place it after another, existing line. To
add this lines to the end of the list, all you have to do is
.
.
.
struct line *last, *linetoinsert;
last = getlastline();
insertafterline(linetoinsert, last);
.
.
.
Which will put linetoinsert after the last line in the list.
If there are no links existing yet, then getlastline() will
return NULL, and insertafterline() will understand this to mean
"put it at the end."
insertafterline() isn't restricted to adding to the end, you
could insert after, say, the fifth element, and make a new
sixth element. This would have the effect of pushing
everything after the sixth up one, but of course, they wouldn't
Issue 15 C News 10
actually have to move at all.
[insertbeforeline]
insertbeforeline() works in much the same was as
insertafterline() does. If you wanted to make a new first line
in the list, you'd just have to call getfirstline(), and then
insertbeforeline() like the previous example.
The next group of functions delete lines from within the list.
deleteline
Calling deleteline() and telling it which line you want deleted
(by passing the pointer to it), will free the memory occupied
by the line, and if string was allocated, it'll free that as
well. Then it will patch up all the prevline and nextline
pointers that are related to the record you're deleting.
deletealllines
deletealllines() will go through, and free up all of the
structures allocated by getnewline(), and reinitialize
everything so that you can start a new list.
The last group of functions in the library move lines from
place to place in the list. Mostly, this is done through calls
to insertbeforeline, insertafterline, and deleteline. They do
some housekeeping, though, to make sure that everything is in
order.
[movebeforeline]
This will take a line *that's already in the list*, and move it
to another location, before another line. Results are
unpredictable if you tell it to move a line that's not in the
list somewhere.
[moveafterline]
This does the same thing as movebeforeline(), except that it
will put the line you want to move after another line, not
before it. Same restriction applies with respect to lines not
already in the list.
4 The Example Program
The example program gives you an idea of how to use these
functions in real life. It creates some lines of text, makes a
list of them, moves them, deletes them, inserts them, and
prints them, so that you can see what the results are.
Issue 15 C News 11
5 Winding Down
Well, that's about it for linked lists. I wrote the library a
few months back for a terminate and stay resident (TSR) text
editor, which never got off the ground. If anybody would like
to do an article on writing TSRs in Microsoft 'C, I'd be very
thankful <grin>.
There are certainly things that could be added to this
library. For starters, it can only handle one linked list at a
time. What if you wanted to open two files at the same time?
A possible way to deal with that is to put everything in an
outer, enveloping structure. That way, you could specify which
list you'd like to work with for all of the insert, delete, and
move commands.
I'd be glad to do more of these articles, if people find them
educational.
Anthony Lander
-----
5637 Eldridge Ave, Fidonet 1:163/115.4
Montreal, Quebec, Alternet 7:483/4
CANADA H4W 2C9 Compuserve 74017,544
Issue 15 C News 12
================================================================
BEGINNERS CORNER: By Wayne Dernoncourt
================================================================
This article is scheduled to discuss why the separate steps of
editing the code, compiling, linking and finally running are
needed to writing a program in C. This discussion isn't
restricted to C, and can be applied to other languages.
In some versions of some languages, there is no need to edit
the program separately. All editing is done within the
language itself. For example, one system that I've used (a
Hewlett-Packard 9830) came up in BASIC, the operating system
(such as it was) revolved around BASIC. The computer would
check each line for syntax errors as it was being entered and
wouldn't accept a line with syntax errors. When you wanted to
run the program, you would simply issue the RUN command and
the computer started running. The only problem with this
approach was that it was incredibly slow (it took about 45
seconds to do a FOR-NEXT loop with a thousand iterations and
nothing in it!!). This approach is called an interpreter.
That is the machine must examine each line of a program and
decode the characters on the line for instructions and then
execute the instructions. This approach isn't much of a
problem if a program is being developed and debugged. This
approach has advantages because it is relatively simple to
write an interpreter and easy to debug in this environment.
Interpreters on systems that are now common are much faster,
but they're still relatively slow when compared to the other
techniques to be discussed.
One way to speed this up is to "tokenize" the program. That
is, take each line of the program and convert the BASIC
commands to a sort of shorthand for the computer. This
eliminates the first step of the interpretive process used
above, that of decoding the ASCII character strings into
commands for the BASIC interpreter. This is the process used
by the BASIC interpreter that comes with most PC's. The
program must be written and edited with the BASIC compiler
(it's tokenized as it's written). You can't use your favorite
text editor or a programming editor (they don't tokenize).
Once you have used an editor to create a program, either a
standalone or one that's integrated with a language, you may
have to compile it. I say may because some integrated
languages are true interpreters that need no compiling. But
lets talk about those that need compiling. Whenever a program
is compiled and linked, it is almost guaranteed to run faster
than one written in an interpretive language (if the compiler
is a production quality compiler). This is because the
computer doesn't have to have an interpreter examine the
Issue 15 C News 13
source or tokenized file for commands.
In addition, some compilers will examine the source code for
code that has no function (the FOR-NEXT loop mentioned above,
that didn't do anything) and eliminate it or code that is
unreachable. That is code that has an unconditional GOTO
before it and either no statement label before or an
unreferenced statement label. Compilers will also perform
other types of code optimization. The compiler will examine
the file that contains the source code (for example:
EXAMPLE.C) and produce a file called the object file (in this
case EXAMPLE.OBJ). This file contains machine language
instructions (actual instructions to the CPU) and also
contains function calls to system routines to do things such
as program initialization, I/O and program termination. The
compiler knows what these function calls are, but doesn't know
the address of where they 'live'. The location of the
function calls can vary from system to system. The function
of the linker is to resolve these last differences. The
linker reads the object file and produces a file that is ready
to run. This file can have a number of different types of
extensions depending on the operating system.
This column was also supposed to discuss some debugging
techniques. The best debugging technique that I've ever come
across is not to make any mistakes. Since that isn't terribly
practical, the next best thing is to keep your mistakes small
and easily manageable. This is done by starting out with a
good, solid design (see the first article). Let's continue
with some practical advice:
The first thing is damage control. If your program is written
so that each of your function calls only does one thing and
then return. You'll be making your life easier during the
debugging phase.
Test each function fully before you start using it in your
program. Create a short main program that only calls the
function that you've created and pass it data and check the
results. You should already have come up with what the
results should be before you started. If the result differs
from what you expected, find out what is wrong (you may have
made an error in your calculations). This is much easier to do
at this stage of the game rather than when you're trying to
get the program working.
A short analogy may be in order here. If you're building a
sports car and you're currently assembling the engine, you'd
examine the pieces to make sure that they were good before you
installed them. Can you imagine how much time, labor and
money you could save yourself if you found a bent crankshaft
when you're installing it instead of once you've poured oil
Issue 15 C News 14
into the engine and have it come out in a puddle at your
feet. The important thing is catch the errors while they're
still small and easy to fix.
The last tip that I have is to use a symbolic debugger. The
VAX and Turbo-C v2.0 both have full screen symbolic debuggers,
while the Prime has a symbolic debugger. A symbolic debugger
will let you 'step' through a program stopping on each source
line and examine variables. Alternatively you can have the
program run until a certain variable is accessed or changed.
The full screen aspect of the debugger (not available on the
Prime) is that the source code is always in view on the screen
at the currently executing line and you can have some of the
user selected variables displayed on the screen. The exact
method varies from system to system.
Wayne
Issue 15 C News 15
================================================================
BEGINNERS CORNER PT II: By Wayne Dernoncourt
================================================================
If this is March, it's time for the column about the MAKE
utility. Before I do that let me discuss something rather
basic about writing a program. No one new to a language can
learn to write a masterpiece on their first attempt. My advice
is to write some simple programs to understand some of the
simple mechanics of what is going on in your program. If you
have nothing else, use variations on the ones that I present to
you.
Now on with the regularly scheduled portion of our show, the
MAKE utility. For this, we have to refer back to the January
article. In that article we discussed putting each function
into it's own file. We wanted to do this to make it easier to
debug a program. Each function can be verified as working
correctly by itself. This left us with a rough time of
compiling the program, so I had you concatenate the files
together. Let's go back and separate them out again, and I'll
show you a neat way to compile and link them together.
The first thing that you have to do (besides creating the
source files for the functions), is to create a simple ASCII
file (suggest using EDLIN) and calling it MYPROJ.PRJ. The only
thing important about this is the file type, it should be .PRJ,
for reasons I'll explain shortly. Put the following lines in
the file (each on it's own line)
INIT
GETDATA
COMPUTE
PRINTRESULTS
Notice that the filetype of .C isn't on any of the files. It
doesn't have to be because it's assumed to be of that
filetype. The filenames can be lowercase, the operating system
will change them into uppercase before it does anything else
with them anyway. The order isn't important, the only thing
that matters is that all of the files needed for the main
program are mentioned in the list and spelled correctly.
The next thing you need to do is to get into Turbo-C and the
main routine. Do you see across the top of the screen, on the
left it says File, besides that Edit, then Compile, Run, Proj,
Options & Debug. Use the F-10 key to get to that top menu and
press the P key to highlight the Project item and you'll get a
pull-down menu that says *.PRJ. This indicates that Turbo-C
will list all of the files in the current directory with that
file type, again press return, and the pull-down menu will
Issue 15 C News 16
disappear.
Next time you compile, the compiler will check to see if the
.OBJ file (if it exists) has a date later than the C source
file. If the object file was created after the source file,
the compiler checks the next file in the list. If the object
file was created before the source file, that indicates that
the source file has changed and therefore recompiles the source
to a new object file. After all of the checking & compiling
are done, the linker is called using the files that it just
checked & compiled to link to the main routine.
This facility makes it very useful to create libraries of
commonly used routines and use them. The concept is to build
routines that can be used like building blocks. Each routine
must be debugged before you can use it, but once it is, you can
use it without the worry of writing and debugging it again.
Another useful tool that is becoming popular towards this goal
is the {{prototype}}. A prototype isn't the real thing, but it
represents the real thing. A prototype airplane, for example,
looks like the real airplane, allowing engineers and mechanics
to check for interference and any problems that might occur
during manufacture. A C {{prototype}} has a similar
functionality. It doesn't actually do anything, it doesn't get
called, etc. What it is used for, is to make sure that the
calling routines have the correct number and type of arguments
as the program is being compiled. The default variable type on
functions, both calling and return is the integer. The linker
makes no checks on the number or types of arguments that are
being passed to the called function. This process occurs in
what is called the C pre-processor. A more rigorous version of
this goes on in what is called the LINT utility, that is, lint
as in nit-picking.
The following example, this showing how prototypes are used,
will print a standard heading on a program output for
identification.
This file is called heading.c and contains the following source
lines:
#include "mylib.h"
#include <stdio.h>
void heading (void)
printf ("\n");
printf ("This is a standard heading\n\n");
return;
The file mylib.h contains the actual prototype and has the
Issue 15 C News 17
following single line in it:
void heading(void);
No doubt all of the sharp eyed readers out there noticed that
sometimes the include statement uses quotes and sometimes angle
brackets are used. The quotes are used for user supplied
functions and angle brackets are used for system supplied
functions (like stdio.h). In the actual prototype itself,
there are a couple of words which look familiar, but used in an
unusual manner.
The data type void means, in this case, that no data is passed
into the function and no data is passed out of the function.
That is the whole essence of the prototype, you're telling the
compiler what each function has going into it and coming out of
it as far as the type of data goes. The only thing the
function does (in this case) is modify the appearance of the
screen.
To actually use this function in a program, try the following
test program and see what happens:
#include "mylib.h"
main()
{
printf ("This is a test of the heading function\n");
heading();
}
The reason that the header file (mylib.h) is included in both
the function routine and the main program is to make sure that
both of them match whenever they're recompiled. If one (or
both) changes without the prototype definition changing to
match, an error will be generated. This error checking goes
back to finding errors as soon as possible after you make them,
not waiting until you get the wrong numbers coming out of your
program.
In one of the recent issues, I discussed using the #define
statement, but I was vague. I'll attempt to remedy that now
by providing an example of how #define can be used to make your
programs clearer. This will involve two programs, one using
the defines, the other not.
Both of the following programs are to find the area and
Issue 15 C News 18
perimeter of a circle. The first uses an #include statement
for a file called CIRCLE.H, the second has all of the relevant
arithmetic hardcoded into the program. The #define statement
takes effect during the pre-processor phase of compilation and
functions as a MACRO string substitution facility. All of the
code is placed in line with the surrounding code.
The following three lines are in CIRCLE.H:
#define PI 3.14159
#define PERIMOFCIRCLE(p,d) p=d*PI/2.0
#define AREAOFCIRCLE(a,d) a=d*d*PI/4.0
The main code contains the following lines of code:
#include <stdio.h>
#include "circle.h"
main()
{
float diam, perim, area;
diam = 2.;
PERIMOFCIRCLE (perim, diam);
AREAOFCIRCLE (area, diam);
printf ("Diameter: %f\nPerimeter: %f\nArea: %f\n", diam,
perim, area);
}
or:
#include <stdio.h>
main()
{
float diam, perim, area;
diam = 2.;
perim = 1.570795*diam;
area = 0.7853975*diam*diam;
printf ("Diameter: %f\nPerimeter: %f\nArea: %f\n", diam,
perim, area);
}
Of course this is an extreme example. The code isn't commented
in any way (this isn't a recommended coding practice), but it
does make the point that you can make your life easier if you
put symbols (like PI) in for common things in your program.
Both of the Prime and DECUS user groups have developed versions
of the MAKE utility for their respective systems, but I have
never had a chance to use them. Prototypes are available on
the VAX, but aren't available on the Prime using the current
version of C that we have on the system.
Issue 15 C News 19
C ya Next Month.....
Wayne
Issue 15 C News 20
================================================================
ARTICLE SUBMISSION STANDARDS
================================================================
All articles, reviews and letters to editor should be
submitted in a ASCII formatted file. Please use 0-65 margins,
and single space. Do not format the text in anyway, as I use
Proff to format C News. Proff takes care of the justification,
footnotes and headers.
You can send in your article on a diskette to the C BBS,
or upload it to the C BBS. See "How to Contact us here at C
News" for more information.
Barry
Issue 15 C News 21
================================================================
HOW TO GET HOLD OF US HERE AT CNEWS
================================================================
The primary address for C News is as follows:
C News
% BCL Limited
P.O. Box 9162
McLean, VA 22102
USA
The primary electronic address for C News is the C BBS:
C BBS
1-703-644-6478
2400,8,N,1 23hrs a day.
1:109/307 in Fidonet.
The secondary electronic address for C News is:
MCI Mail: BCL Limited
Barry
